#include <fstream>
using namespace std;

template <class ItemType>
class EnhancedQueue;

template <class ItemType>
class NodeType;

template <class ItemType>
class NodeType
{
	friend class EnhancedQueue<ItemType>;

public:
	NodeType();
	NodeType(const ItemType &value);

private:
	ItemType info;
	NodeType<ItemType> *next;
};

template <class ItemType>
NodeType<ItemType>::NodeType()
{
	next = NULL;
}

template <class ItemType>
NodeType<ItemType>::NodeType(const ItemType &value)
{
	info = value;
	next = NULL;
}

template <class ItemType>
class EnhancedQueue   
{
public:


    EnhancedQueue();		
    //default constructor

	~EnhancedQueue();
	//deconstructor

    EnhancedQueue(const EnhancedQueue &orig);		
    //copy constructor

    EnhancedQueue operator=(const EnhancedQueue<ItemType>& rhs);
    //assignment operator

    int  Length() const;
    //Pre:  none.
    //Post: returns the number of elements in the queue.
  
    void Clear();
    //Pre:  none.
    //Post: clears the queue.

    void MoveLastToFront();
    //Pre:  none.
    //Post: moves the last item to the front of the queue.

    bool Move(int from, int to);
    //Pre:  none.
    //Post: relocates the item in the queue

    void Enqueue(ItemType item);
    //Pre:  none.
    //Post: the item is added at the end of the queue.

    int Find(ItemType item);
    //Pre:  none.
    //Post: the position of the item is returned if found
	//      -1 is returned if not found.

    void Dequeue(ItemType &item);
    //Pre:  the queue is not empty.
    //Post: first item is removed from the queue

    void Print(ostream &out);
    //Pre:  none.
    //Post: the contents of the queue is printed

    bool Delete(int pos, ItemType &item);
    //Pre:  none.
    //Post: the item at the position is deleted
	//      and its value is passed by reference

private:

	NodeType<ItemType>* queueData;
	int length;

};

#include "queue.cpp"